不难发现到就是长度为 子串的 的最大值。
根据一个性质后缀自动机的一个点的 被他的后继分为了很多部分,所以我们可以用,处理出它的。
接着是统计答案,显然我们可以用线段树覆盖。
但是,我们并不需要将对于每个点将 到 更新一遍,而是只更新,最后循环倒着处理。(因为一个字符串如果包含最长的字串有次,那么它包含更短的子串肯定有次)
这样就可以解决了。
#include <cstdio>
#include <cstring>
#include <iostream>
using namespace std;
const int MAXN = 250000 , MAXK = 26;
struct Suffix_Automaton {
int Root , Size , Last , len , Maxlen[ 2 * MAXN + 5 ];
int Trans[ 2 * MAXN + 5 ][ MAXK + 5 ] , Link[ 2 * MAXN + 5 ];
long long dp[ 2 * MAXN + 5 ] , Tag[ 2 * MAXN + 5 ];
Suffix_Automaton( ) { Root = Size = Last = 1; }
void Copy( int u , int v ) {
for( int i = 1 ; i <= MAXK ; i ++ )
Trans[ u ][ i ] = Trans[ v ][ i ];
}
void Extend( int chr ) {
int Newnode = ++ Size , u = Last;
Maxlen[ Newnode ] = Maxlen[ u ] + 1; dp[ Newnode ] = 1;
for( ; u && !Trans[ u ][ chr ] ; u = Link[ u ] )
Trans[ u ][ chr ] = Newnode;
if( !u ) Link[ Newnode ] = 1;
else {
int v = Trans[ u ][ chr ];
if( Maxlen[ v ] == Maxlen[ u ] + 1 ) Link[ Newnode ] = v;
else {
int w = ++ Size;
Copy( w , v ); Maxlen[ w ] = Maxlen[ u ] + 1;
for( ; u && Trans[ u ][ chr ] == v ; u = Link[ u ] ) Trans[ u ][ chr ] = w;
Link[ w ] = Link[ v ];
Link[ v ] = Link[ Newnode ] = w;
}
}
Last = Newnode;
}
void Build( char *str ) {
len = strlen( str );
for( int i = 0 ; i < len ; i ++ )
Extend( str[ i ] - 'a' + 1 );
Sort( );
}
int tot[ 2 * MAXN + 5 ] , Topu[ 2 * MAXN + 5 ];
void Sort( ) {
for( int i = 1 ; i <= Size ; i ++ ) tot[ Maxlen[ i ] ] ++;
for( int i = 1 ; i <= Size ; i ++ ) tot[ i ] += tot[ i - 1 ];
for( int i = 1 ; i <= Size ; i ++ ) Topu[ tot[ Maxlen[ i ] ] -- ] = i;
}
void Dp( ) {
for( int i = Size ; i >= 1 ; i -- ) {
int u = Topu[ i ];
dp[ Link[ u ] ] += dp[ u ];
Tag[ Maxlen[ u ] ] = max( Tag[ Maxlen[ u ] ] , dp[ u ] );
}
}
void Work( ) {
for( int i = len ; i >= 1 ; i -- ) Tag[ i ] = max( Tag[ i ] , Tag[ i + 1 ] );
for( int i = 1 ; i <= len ; i ++ ) printf("%d\n",Tag[ i ]);
}
}SAM;
char str[ MAXN + 5 ];
int main( ) {
scanf("%s", str );
SAM.Build( str ); SAM.Dp( );
SAM.Work();
return 0;
}